﻿// 4872. 最短路之和.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://www.acwing.com/problem/content/4875/

给定一个 n
 个点的加权有向图，点的编号为 1∼n
。

图中任意两点之间都有两条方向相反的边连接两点。

从点 i
 到点 j
 的边的长度为 aij
。

给定一个 1∼n
 的排列 x1,x2,…,xn
。

你需要对该图依次进行 n
 个操作。

其中，第 i
 个操作是将点 xi
 以及该点的所有入边和出边从图中移除。

在执行每一个操作之前，你还需要进行如下计算：

对于每个当前剩余点对 (u,v)
，计算从点 u
 到点 v
 的最短路长度。
将这些最短路长度全部相加得到最短路之和。
注意：

剩余点对 (u,v)
：两个还未被移除的点 u,v
（u≠v
）组成的点对。
(u,v)
 和 (v,u)
 是两个不同点对，需分别计算最短路长度并计入最短路之和。
n
 个操作是按顺序依次执行的，前面的操作会对后面的计算产生影响。
请你输出执行每个操作前计算得到的最短路之和。

输入格式
第一行包含整数 n
。

接下来 n
 行，每行包含 n
 个整数，其中第 i
 行第 j
 个数为 aij
。

最后一行包含 n
 个整数 x1,x2,…,xn
。

输出格式
共一行，输出 n
 个整数，其中第 i
 个整数表示执行第 i
 个操作之前，计算得到的最短路之和。

数据范围
前 4
 个测试点满足 1≤n≤4
。
所有测试点满足 1≤n≤500
，1≤aij≤105
，aii=0
，1≤xi≤n
，保证 x1∼xn
 是一个 1∼n
 的排列。

输入样例1：
1
0
1
输出样例1：
0
输入样例2：
2
0 5
4 0
1 2
输出样例2：
9 0
输入样例3：
4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3
输出样例3：
17 23 404 0

*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 